package q47_permuteUnique;

import java.util.*;

public class Solution_3 {

    private List<Integer> path = new ArrayList<>();
    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {

        Arrays.sort(nums);

        boolean[] used = new boolean[nums.length];
        dfs(nums, used);
        return res;
    }


    /**
     * 在具有重复元素的情况下寻找全排列
     */
    private void dfs(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }


        /*
        我们用set的方式也能够实现同层的去重
        只是效率相较于使用used数组标记会低一点
         */
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {

            if (!used[i] && !set.contains(nums[i])) {
                used[i] = true;
                path.add(nums[i]);
                set.add(nums[i]);
                dfs(nums, used);
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }

    }
}
